package Heap;

public class MyHeap {
    public int[] arr;
    public int size;

    public MyHeap(int capacity) {
        arr = new int[capacity];
    }

    public MyHeap(int[] arr) {
        this.arr = arr;
        this.size = arr.length;
        heapify();
    }

    //获取栈顶元素
    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return arr[0];
    }

    //删除堆顶元素
    public int poll() {
        if (isEmpty()) {
            return 0;
        }
        int t = arr[0];
        arr[0] = arr[size - 1];
        size--;
        //下潜
        down(0);

        return t;
    }

    //指定删除元素
    public int poll(int i) {
        if (i > size) {
            return 0;
        }
        int temp = arr[i];
        arr[i] = arr[size - 1];
        size--;
        //下潜
        down(i);
        return temp;
    }

    //替换堆顶元素
    public void replace(int i) {
        if (isEmpty()) {
            return;
        }
        arr[0] = i;
        down(0);
    }


    //添加元素
    public boolean offer(int value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (size - 1) / 2;
        while (i > 0 && arr[j] < value) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

    //建堆
    public void heapify() {

        //先找到最后非叶子节点
        int lastNonLeafNodes = size / 2 - 1;
        for (int i = lastNonLeafNodes; i >= 0 ; i--) {
            //下潜
            down(i);
        }
    }

    //下潜
    public void down(int i) {
        int left = 2 * i + 1;
        int right = left + 1;
        int max = i;
        if (left < size && arr[left] > arr[max]) {
            max = left;
        }
        if (right < size && arr[right] > arr[max]) {
            max = right;
        }
        if (max != i) {

            //交换
            swap(i,max);

            //继续下潜
            down(max);
        }
    }

    //交换
    public void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    //判断是否为空数组
    public boolean isEmpty() {
        return size == 0;
    }

    //判断是否为满数组
    public boolean isFull() {
        return  size == arr.length;
    }
}
